# -*- coding: utf-8 -*-

"""剑指 Offer II 067. 最大的异或
给定一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。

示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：
输入：nums = [0]
输出：0

示例 3：
输入：nums = [2,4]
输出：6

示例 4：
输入：nums = [8,10,2]
输出：10

示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：
1 <= nums.length <= 2 * 10^4
0 <= nums[i] <= 2^31 - 1

进阶：你可以在 O(n) 的时间解决这个问题吗？"""


class TrieNode():
    def __init__(self) -> None:
        self.children = [None, None]
        self.isEnd = False


class Solution:
    """本题的关键在于明白 异或 运算的逻辑意思：异或 -> 找不同
    所以本题的意思就是找 nums[j]，与前面 [0, j] 个数字的不同程度，那么换为32为二进制，前面不够的用0填充，
    对于 一对多的搜索，可以用前缀树解决"""
    def findMaximumXOR(self, nums) -> int:
        trie = TrieNode()
        diff = {'0':'1', '1':'0'}
        
        max_xor = 0
        for num in nums:
            # 构建32位二进制字符串
            if num:
                bits32 = '0'*(32-num.bit_length())+bin(num)[2:]
            else:
                bits32 = '0'*32
            
            # 添加到前缀树
            node = trie
            for b in bits32:
                if not node.children[int(b)]:
                    node.children[int(b)] = TrieNode()
                node = node.children[int(b)]
            node.isEnd = True

            # 搜索前缀树中与 num 最不同的路径，先看看不同的，实在没有不同的，再选择相同的
            node, xor = trie, ''
            for b in bits32:
                xb = diff[b]
                if node.children[int(xb)]:
                    node = node.children[int(xb)]
                    xor += xb
                else:
                    node = node.children[int(b)]
                    xor += b

            # 重置全局差异
            max_xor = max(num ^ int(xor, 2), max_xor)
        
        return max_xor
        

if __name__ == '__main__':
    so = Solution()
    print(so.findMaximumXOR([3,10,5,25,2,8]))
    print(so.findMaximumXOR([0]))
    print(so.findMaximumXOR([2,4]))
    print(so.findMaximumXOR([8,10,2]))
    print(so.findMaximumXOR([14,70,53,83,49,91,36,80,92,51,66,70]))
